#pragma  once
#include "map"
#include "vector"
#include "iostream"
#include "queue"
#include "algorithm"
#include "stack"
#include "DijkstraTable.hpp"
#include "PrimData.hpp"
#include "string"
#include "fstream"
#include "set"
#include "UnDirGraph.hpp"
#include "list"
#include "Mat.hpp"

// python中是实现是双重字典,这里仿照python的实现方式.

template<class V ,class E = double> // 其中V表示顶点的信息,E表示边的信息
class Graph
{
public:
    E m_empty; //设置默认的零值

    Graph()=default;

    explicit Graph(std::vector<V> v,E empty = 0)
    {
        m_empty = empty;
        for(auto & p : v) {
            std::map<V,E> tmp;
            m_data[p]= tmp;
        }
    }
    Graph(const Graph<V,E> &G2)
    {
        this->m_data = G2.m_data;
        this->m_empty = G2.m_empty;
    }

    Graph<V,E>& operator = (const Graph<V,E>  & G2)
    {
        if (this == &G2) {
            return *this;
        }else{
            this->m_data = G2.m_data;
            this->m_empty = G2.m_empty;
        }
        return *this;
    }


    void addMatrix(std::vector<std::vector<E>> matrix)
    {
        // 通过邻接矩阵构建最终结果
        auto Nodes = getNodes();
        for(int i = 0;i < matrix.size();i ++){
            for(int j = 0; j < matrix.size();j ++){
                m_data[Nodes[i]][Nodes[j]] = matrix[i][j];
            }
        }

    }

    virtual bool operator == (Graph<V,E> G2)
    {
        for(auto [key1,value1] : m_data){
            for(auto [key2,value2] : value1){
                if( m_data[key1][key2] != G2.m_data[key1][key2] ){
                    return false;
                }
            }
        }
        return true;
    }
    void Draw()
    {
        write2Dot("../temp.dot"); //输出文件
        system("dot -Tpng ../temp.dot -o ../temp.png");
    }
    void undirected() //给出一侧,做对称化操作
    {
        for(auto [key1,value1] : m_data){
            for(auto [key2,value2] : value1){
                if(m_data[key1][key2] != m_empty){
                    m_data[key2][key1] = m_data[key1][key2]; //如果m_data有这个键,则修改;如果没有则增加
                }
            }
        }
    }

    virtual void print()
    {
        for(auto & p : m_data){
            std::cout<<"[" << p.first << ", ";
            for(auto & q: p.second){
//                if(q.second != m_empty)
                    std::cout << q.first << ":"<< q.second << " ";
            }
            std::cout << "]\n";
        }
    }

    virtual void addEdge(V v1, V v2,E e)
    {
        m_data[v1][v2] = e;
        if(m_data.find(v2) == m_data.end()){
            m_data[v2] = std::map<V,E>(); //创建空的节点
        }
    }

    virtual bool isGraphConnected()
    {
        // 判断图是否连通
        std::vector<V> Nodes = this->getNodes(); //通过下标映射到V
        int N = Nodes.size();
        //创建 标志向量
        std::map<V,int> flag;
        for(int i = 0 ; i < N ; i++ ){
            flag[Nodes[i]] = 0;
        }
        std::stack<V> sta; //栈数据结构
        sta.push(Nodes[0]);
        flag[Nodes[0]] = 1;
        int count = 1;
        while(!sta.empty()){
            int End = 0;
            for(auto [key,value] : m_data[sta.top()]){
                if(flag[key] == 0){
                    count ++;
                    flag[key] = 1;
                    sta.push(key);
                    End = 1;
                    break;
                }
            }
            if(End == 0){
                sta.pop(); //弹出元素
            }

        }
        if(count == N){return true;}
        else {return false;}
    }

    void addNode(V v1)
    {
        m_data[v1] = std::map<V,E>(); //添加空节点
    }

    void addNodesFrom(std::vector<V> vec)
    {
        for(auto & p : vec){ //添加一列空节点
            m_data[p] = std::map<V,E>();
        }
    }

    virtual void addEdgesFrom(std::vector<V>  vec1, std::vector<V>  vec2 , E e)
    {
        if(vec1.size() != vec2.size()) {
            throw std::invalid_argument("vec1 ,vec2 大小不一致");
        }
        for(int i = 0; i < vec1.size() ; i++){
            m_data[vec1[i]][vec2[i]] = e;
        }
    }

    void BFS()//Breadth First Search
    {
        std::vector<V> Nodes = this->getNodes(); //通过下标映射到V
        int N = Nodes.size();
        //创建 标志向量
        std::map<V,int> flag;
        for(int i = 0 ; i < N ; i++ ){
            flag[Nodes[i]] = 0;
        }
        std::queue<V> que ; //保存需要遍历的节点
        que.push(Nodes[0]);
        while(!que.empty()){
            flag[que.front()] = 1; //已经访问当前的节点
            for(auto [key,value] : m_data[que.front()]){
                if(flag[key] == 0){
                    que.push(key);
                    flag[key] = 1;
                }
            }
            std::cout << que.front() << " ,";
            que.pop();
        }

    }

    virtual void DFS() //深度优先搜索算法
    {
        std::vector<V> Nodes = this->getNodes(); //通过下标映射到V
        int N = Nodes.size();
        //创建 标志向量
        std::map<V,int> flag;
        for(int i = 0 ; i < N ; i++ ){
            flag[Nodes[i]] = 0;
        }
        std::stack<V> sta; //栈数据结构
        sta.push(Nodes[0]);
        flag[Nodes[0]] = 1;
        std::cout << Nodes[0] << ",";
        while(!sta.empty()){
            int End = 0;
            for(auto [key,value] : m_data[sta.top()]){
                if(flag[key] == 0){
                    std::cout << key << ",";
                    flag[key] = 1;
                    sta.push(key);
                    End = 1;
                    break;
                }
            }
            if(End == 0){
                sta.pop(); //弹出元素
            }

        }

    }
    std::vector<V> getNodes()
    {
        std::vector<V> nodes(m_data.size());
        auto iter = m_data.begin();
        for(int i = 0; i < m_data.size();i ++){
            nodes[i] = iter->first;
            iter ++;
        }
        return nodes;
    }



    std::vector<V> Dijkstra(V v1, V v2,E defaultMax = 10000) //Dijkstra 算法,其中v1,v2分别表示起始点和终止点
    {
        auto table = createDijkstraTable(v1,defaultMax);
        std::vector<V> nodes;
        nodes.push_back(v2);
        V vx = table.pNode(v2);
        nodes.push_back(vx);
        while(vx != v1){
            vx = table.pNode(vx);
            nodes.push_back(vx);
        }
        std::reverse(nodes.begin(),nodes.end());
        return nodes;
    }

    virtual bool write2Dot(const std::string& filename)
    {
        std::fstream outFile;
        outFile.open(filename,std::ios::out);
        // 检查文件是否成功打开
        if (!outFile) {
            std::cerr << "无法打开文件" << std::endl;
            return false;  // 返回错误代码
        }

        outFile << "digraph G { \n node [shape=ellipse, color=blue, style=filled, fontcolor=white];\n"
                   "    edge [color=gray]; \n";

        auto nodes = getNodes();
        for(auto [key1,value1] : m_data){
            for(auto [key2,value2] : value1){
                outFile << key1 << "->" << key2<<"[label="<<value2 << "]\n";
            }
        }

        outFile << "\n }";
        outFile.close();
        return true;
    }

    std::vector<std::vector<E>> Floyd(E defaultMax = 10000) //Floyd算法 ,返回一个二维数组
    {
        auto Nodes = getNodes();
        int N = Nodes.size();
        std::vector<std::vector<E>> mat(N);
        for(int ii = 0; ii < N ;ii ++){
            V i = Nodes[ii];
            mat[ii].resize(N);
            for(int jj = 0 ;jj < N ; jj++){
                V j = Nodes[jj];
                if(jj == ii){
                    mat[ii][jj] = 0;
                }else if (m_data[i].find(j) != m_data[i].end()){
                    mat[ii][jj] = m_data[i][j];
                }else {
                    mat[ii][jj] = defaultMax;
                }
            }
        }
        // 更新节点
        for(int k = 0;k < N ;k++){
            for(int i = 0; i < N ; i++){
                for(int j = 0; j < N ;j ++){
                    mat[i][j] = std::min(mat[i][j],mat[i][k]+mat[k][j]);
                }
            }
        }

        return mat;
    }
    virtual E sumWeight()
    {
        E sum = 0;
        for(auto [key1,value1] : m_data){
            for(auto [key2,value2] : value1){
                sum += m_data[key1][key2];
            }
        }
        return sum;
    }
    std::map<V,E> Bellman_Ford(V v1,E defaultMax = 10000)//单源算法,比Dijkstra算法效率低,但是可以处理负权的情况
    {
        //返回从顶点v1出发到各个节点的最短路径
        std::map<V,E> record;
        auto Nodes = getNodes();
        int N = Nodes.size();
        for(int i = 0; i < N ; i++){
            record[Nodes[i]] = defaultMax;
        }
        record[v1] = 0;
        bool end = false;
        // 核心算法,松弛算法
        for(int i = 0; i < N-1 ;i ++ ){
            bool inner_flag = false; //内部标记,如果发生变化则说明需要继续执行,否则break出循环
            for(auto [key1,value1] : m_data){
                for(auto [key2,value2] : value1){
                    if( record[key1] + value2 < record[key2]  ){
                        inner_flag = true;
                        record[key2] = record[key1] + value2;
                    }
                }
            }
            if(!inner_flag){
                end = true;
                break;
            }
        }

        if(!end){
            std::cerr << "Error, negative weight appeared.\n ";
            return record;
        }
        return record;
    }

    bool isNodeCycle(V v1)
    {
        if(m_data[v1].size() == 0){
            return false; //如果这个节点没有后继节点,就是无环
        }
        std::vector<V> Nodes = this->getNodes(); //通过下标映射到V
        int N = Nodes.size();
        //创建 标志向量
        std::map<V,int> flag;
        for(int i = 0 ; i < N ; i++ ){
            flag[Nodes[i]] = 0;
        }
        std::queue<V> que ; //保存需要遍历的节点
        que.push(v1);
        while(!que.empty()){
            flag[que.front()] = 1; //已经访问当前的节点
            for(auto [key,value] : m_data[que.front()]){
                if(key == v1){
                    return true;
                }
                if(flag[key] == 0){
                    que.push(key);
                    flag[key] = 1;
                }
            }
            que.pop();
        }
        return false;
    }

    bool is2NodesConnected(V v1, V v2)
    {
        std::vector<V> Nodes = this->getNodes(); //通过下标映射到V
        int N = Nodes.size();
        //创建 标志向量
        std::map<V,int> flag;
        for(int i = 0 ; i < N ; i++ ){
            flag[Nodes[i]] = 0;
        }
        std::queue<V> que ; //保存需要遍历的节点
        que.push(v1);
        while(!que.empty()){
            flag[que.front()] = 1; //已经访问当前的节点
            for(auto [key,value] : m_data[que.front()]){
                if(flag[key] == 0){
                    que.push(key);
                    flag[key] = 1;
                    if(key == v2){
                        return true;
                    }
                }
            }
            que.pop();
        }
        return false;
    }
    bool isDGA()
    {
        //是否是有向无环图
        auto Nodes = getNodes();
        for(auto node : Nodes){
            if(isNodeCycle(node)){ //遍历所有的节点,如果所有的节点都是没有环,则整个图就是有向无环图
                return false;
            }
        }
        return true;
    }
    std::list<std::vector<V>> findALLPath(V v1, V v2)
    {
        //找到从v1到v2的路径所有路径

    }
    E naive_Ford_Fulkerson(V start , V end)
    {
        // 简单求解器下的最大流问题,但是最终结果可能不是全局最优解.


    }
    bool mins(std::vector<V> path, E e)
    {
        // 在path路径上减去e,如果减到零则删除这条边,如果小于0则报错
        for(int i = 0;i < path.size() - 1; i ++ ){
            if (m_data[path[i]][path[i+1]] > e){
                m_data[path[i]][path[i+1]] -= e;
            }else if(m_data[path[i]][path[i+1]] == e){
                m_data[path[i]].erase(path[i+1]);
            }else{
                return false;
            }
        }
        return true;

    }
    E path_min(const std::vector<V> & path )
    {
        // 返回这条路径上的最小值
        E emin = 10000;
        for(int i = 0; i < path.size() - 1; i ++){
            if(m_data[path[i]][path[i+1]] < emin){
                emin = m_data[path[i]][path[i+1]];
            }
        }
        return emin;
    }

    void addBackwardPath(std::vector<V> path, E e)
    {
        // 在path这条路径的反向路径上,添加上元素e.并且当有重复边时需要merge
        int N = path.size();
        for(int i = N-1; i > 1; i --){
            if(m_data[path[i]].find(path[i-1]) != m_data[path[i]].end()){
                m_data[path[i]][path[i-1]] += e; //Merge的过程
            }else{
                m_data[path[i]][path[i-1]] = e;
            }

        }
    }

    E Ford_Fulkerson(V start , V end) //最大流问题
    {
        E Emax = 0;
        // 创建残差图
        Graph<V,E> G;
        G = *this;

        while(G.is2NodesConnected(start,end)){
            // 首先找到一跳路径,返回这条路上的最大值
            std::vector<V> path = G.Dijkstra(start,end);
            E emin_path = G.path_min(path);
            if (G.mins(path,emin_path) == false){
                std::cerr << "出现错误 \n";
            }
            G.addBackwardPath(path,emin_path); //添加反向的边
            Emax += emin_path;
        }
        return Emax;
    }

    E naiveHungarianAlgorithm()
    {
        // 这里通过排列组合实现匈牙利算法,效率非常低
        auto Nodes = getNodes();
        int N = Nodes.size();
        if(N > 10){
            std::cerr << "节点数过大(超过10),终止计算\n";
            exit(0);
        }
        std::vector<int> range(N);
        for(int i = 0;i < N;i ++ ){
            range[i] = i;
        }
        std::vector<std::vector<int>> sumArrange;
        std::vector<E> sumArrangeScore;//得分
        do{
            auto vec = std::vector<int>(range.begin(),range.end());

            E score = 0;
            for(int i = 0;i < N;i ++){
                score += m_data[Nodes[i]][Nodes[vec[i]]];
            }
            sumArrange.push_back(vec);
            sumArrangeScore.push_back(score);
        }while(std::next_permutation(range.begin(),range.end()));

        // 打印最大值值的取法
        int pos = std::max_element(sumArrangeScore.begin(),sumArrangeScore.end()) - sumArrangeScore.begin();
//        std::cout << "取法: " << "\n";
//        for(auto p : sumArrange[pos]){
//            std::cout << p << std::endl;
//        }
//        std::cout << "匈牙利算法的最大值 :" << *std::max_element(sumArrangeScore.begin(),sumArrangeScore.end()) << std::endl;
        return *std::max_element(sumArrangeScore.begin(),sumArrangeScore.end());
    }

    E HungarianAlgorithm(bool isMin = true) //参数表示求最大还是最小,默认是最小
    {
        // 第一步,将map -> mat形式,后面的匈牙利算法都在矩阵上操作
        auto Nodes = getNodes();
        int N = Nodes.size();
        Mat<E> mat(N,N),raw_mat(N,N);
        for(int i = 0 ;i < N ;i ++ ){
            for(int j = 0; j < N; j ++){
                if(isMin){
                    mat(i,j) = m_data[Nodes[i]][Nodes[j]];
                }else {
                    mat(i,j) = -m_data[Nodes[i]][Nodes[j]];
                }
            }
        }
        raw_mat = mat;
        // 第二步 每一行减去这一行的最小值,每一列减去这一列的最小值
        auto RowMin = mat.RowMin();
        for(int i = 0; i < N ;i ++){
            mat.apply([&](int a){return a-RowMin(i);},i,true);
        }
        auto ColMin = mat.ColMin();
        for(int i = 0; i < N ;i ++){
            mat.apply([&](int a){return a-ColMin(i);},i,false);
        }
        // mat.print();
        // 第三步
        // 计算包含0的所有元素个数
        auto cover = mat.minimumSetCoveringZeros();
//        std::cout << "计算零元素在横轴上的个数\n";
//        for(auto x : cover.setRow){
//            std::cout << x << ",";
//        }
//        std::cout << std::endl;
//        std::cout << "计算零元素在纵轴上的个数\n";
//        for(auto y : cover.setCol){
//            std::cout << y << ",";
//        }
//        std::cout << "统计所有零元素的个数:" << cover.CoverZeroNum << std::endl;

        while(cover.size() < N){
            mat.addZero(cover); //这里mat修改过了
            cover = mat.minimumSetCoveringZeros(); //再修改后的mat再计算其覆盖
        }
        // 最后返回的是满足条件的覆盖
        //raw_mat.print();
        auto v = mat.Match();
        int Min = 0;
        for(int i = 0; i < mat.row();i ++){
            Min += raw_mat(i,v[i]);
        }

        if(isMin){
            return Min;
        }else{
            return -Min;
        }

        /*
        找到覆盖所有0元素的最小覆盖
        (返回两个setRow,setCol,分别表示Row上的索引和Col上的索引)
        如果此时 两个索引数之和等于N,则终止迭代.
         如果没有出现,则在找到非覆盖的地方最小值,非覆盖的地方减去这个值,则会出现0.相交的地方加上这个值.
         从而增添0的个数.继续这一过程,直到终止条件.
         得到一个最小覆盖,在这个最小覆盖上找到最终的解,
         返回一个数组v = (v0,v1,...,v{N-1}).计算下列值:
         sum(mat[0,v0],mat[1,v1],...,mat[{N-1},v{N-1}])
         如果 isMin == true,则返回这个值;如果 isMin ==false,则返回相反数
        */


    }

    DijkstraTable<V, E> createDijkstraTable(V v1, E defaultMax = 10000) //Dijkstra 算法,其中v1,v2分别表示起始点和终止点
    {
        std::vector<V> nodes = getNodes();
        DijkstraTable<V, E> table(nodes);
        table.dist(v1) = 0;
        PriorityQueue<V,E> priQue; //优先队列
        priQue.push(Data<V,E>(v1,table.dist(v1)));
        while(!priQue.empty()){
            V current = priQue.top().node; //取出当前需要遍历的元素
            for(auto [key,value] : m_data[current]){
                if( table.dist(key) > table.dist(current) + value ){
                    // 更新节点,再插入节点
                    table.dist(key) = table.dist(current) + value;
                    table.pNode(key) = current;
                    priQue.push(Data<V,E>(key,table.dist(key)));
                }
            }
            priQue.pop();

        }
        return table;
    }

protected:
    std::map<V,std::map<V,E>> m_data;
};